// Greedy sequential coloring of the nodes using the      //
// Brelaz saturated coloring idea starting with a clique  //

        
//--------------------------//
// routines for the degrees //
//--------------------------//


void degree()
{ // computes the degrees of the nodes a[1],...,a[m] //
  // computes the degrees of the nodes in snake      // 
  int i,j,t,x;
  
  for (i=1; i<=m; i++) 
  { x=0;
    for (j=1; j<=m; j++) 
    { if (inc[a[i]][a[j]]) { x++; } }
    c[i]=x;   
  }
  // cout << endl; //
  // cout << "degrees" << endl; //   
  // displaysnake(); //
  x=1; i=1;
  while (x==1) 
  { x=0; 
    for (j=1; j<=m-i; j++) 
    { if (c[j]<c[j+1]) 
      { t=a[j]; a[j]=a[j+1]; a[j+1]=t;
        t=c[j]; c[j]=c[j+1]; c[j+1]=t;
        x=1;
      }
    }
    i++;
  }
  // cout << endl; //
  // cout << "ordered degrees" << endl; //
  // displaysnake(); //
}

//-------------------------//
// routines for the clique //
//-------------------------//

void clique()
{ // greedy sequential clique search //
  int i,j,r,s,t,max,pivot,size;
  
  for (i=1; i<=m; i++) { b[i]=a[i]; c[i]=0; }
  size=m; s=0;
  while (size>0) 
  { max=-1;
    for (i=1; i<=size; i++)
    { t=0; pivot=b[i];
      for (j=1; j<=size; j++) { if (inc[pivot][b[j]]) { t++; } }
      if (max<t) { max=t; r=i; }
    }
    s++;
    for (i=1; i<=m; i++) { if (a[i]==b[r]) { c[i]=s; } }
    t=0; pivot=b[r]; 
    for (i=1; i<=size; i++)
    { if (inc[pivot][b[i]]) { t++; b[t]=b[i]; } } 
    size=t;
  }
  // cout << endl; //
  // cout << "clique" << endl; //
  // displayabc(); //
}

void coloring2()
{ // Brelaz's algorithm starting with a clique //
  int i,j,r,t,x,y;
  int max,pivot;
  
  act=0; 
  for (i=1; i<=m; i++) { if (c[i]>0) { act++; } } 
  x=1;
  while (x==1) 
  { x=0; max=-1; 
    for (i=1; i<=m; i++)
    { if (c[i]==0) 
      { for (j=1; j<=act+1; j++) { b[j]=0; }
        pivot=a[i];
        for (j=1; j<=m; j++) { if (inc[pivot][a[j]]) { b[c[j]]=1; } }
        t=0; 
        for (j=1; j<=act+1; j++) { if (b[j]==1) { t++; } }
        if (max<t) { max=t; r=i; }
        x=1;
      }
    }
    for (j=1; j<=act+1; j++) { b[j]=0; }
    pivot=a[r];
    for (j=1; j<=m; j++) { if (inc[pivot][a[j]]) { b[c[j]]=1; } } 
    j=1;
    while (b[j]==1) { j++; }
    c[r]=j;
    if (act<j) { act++; }
  }
  // cout << endl; //
  // cout << "coloring" << endl; //
  // displayabc(); //
}


void multiplicity()
{ // orders the multiplicities of the colors //
  // orders the color classes                //
  int i,j,x,y,t;
  
  x=act;
  for (i=1; i<=x; i++) { b[i]=0; f[i]=i; } 
  for (i=1; i<=m; i++) { if (c[i]>0) { b[c[i]]++; } } 
  // cout << endl; //
  // cout << "multiplicity1" << endl; //
  // displayabc(); //
  y=1; i=1;
  while ((i<=x) && (y==1)) 
  { y=0;
    for (j=1; j<=x-i; j++) 
    { if (b[j]<b[j+1]) 
      { t=b[j]; b[j]=b[j+1]; b[j+1]=t;
        t=f[j]; f[j]=f[j+1]; f[j+1]=t;
        y=1;
      }
    }
    i++;
  }
  // cout << endl; //
  // cout << "multiplicity2" << endl; //
  // displayabc(); //
  for (i=1; i<=x; i++) { b[f[i]]=i; } 
  for (i=1; i<=m; i++) { c[i]=b[c[i]]; }
  // cout << endl; //
  // cout << "multiplicity3" << endl; //
  // displayabc(); //
  y=1; i=1;
  while ((i<=m) && (y==1)) 
  { y=0;
    for (j=1; j<=m-i; j++) 
    { if (c[j]<c[j+1]) 
      { t=c[j]; c[j]=c[j+1]; c[j+1]=t;
        t=a[j]; a[j]=a[j+1]; a[j+1]=t;
        y=1;
      }
    }
    i++;
  }
  // cout << endl; //
  // cout << "multiplicity4" << endl; //
  // cout << setw(4) << act; //
  // displayabc(); //
}


void repeated()
{ // colors the graph repeatedly //
  int i,j,x;
  
  opt=gsize;
  for (i=1; i<=trials; i++)
  {degree(); clique(); coloring2(); multiplicity(); 
    cout << endl;
    cout << setw(9) << i;
    cout << setw(9) << act;
    cout << setw(9) << opt;

    if (act<opt) {

      /*
      for(i=m; i>0; --i){
	for(j=m; j>0; --j)
	  inc_tmp[m-i+1][m-j+1]=inc[a[i]][a[j]];
	c_tmp[m-i+1]=c[i];
      }
      */
      for(int i=1;i<=gsize;++i){
	a_tmp[i]=a[i];
	c_tmp[i]=c[i];
      }
      opt=act; }

  } 
  cout<<endl;

  /*
  for(i=1; i<=m; ++i)
    for(j=1; j<=m; ++j)
      inc[i][j]=inc_tmp[i][j];
  */
  for(int i=1;i<=gsize;++i){
    //a[i]=i;
    a[i]=a_tmp[i];
    c[i]=c_tmp[i];
    //c[i]=0;
    //cout<<i<<":\t"<<a[i]<<"\t"<<c[i]<<endl;
  }

}
